package link;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class leetCode143_reorderList {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        stack.add(2);
        Integer peek = stack.pop();
        System.out.println(peek);
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        reorderList(head);

    }
    public static void reorderList(ListNode head) {
        if(head == null) return;
        List<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null){
            list.add(tmp);
            tmp = tmp.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while (i < j){
            list.get(i).next = list.get(j);
            i++;
            if(i == j) break;
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
